/*
** Routines to processing a configuration list and building a state
** in the LEMON parser generator.
*/

#include "configlist.h"
#include <unordered_set>
#include <algorithm>
#include "config.h"
#include "struct.h"
#include "symbol.h"
#include "set.h"
#include "error.h"
#include "lemon.h"

static Config *freelist = 0;      /* List of free configurations */
static ConfigList g_basis_configs;
static ConfigList g_configs;

struct ConfigHash
{
  /* Hash one configuration */
  unsigned confighash(const Config *a) const
  {
    unsigned h=0;
    h = h*571 + a->rp->index*37 + a->dot;
    return h;
  }

  size_t operator()(const Config* a) const
  {
    return confighash(a);
  }
};

/* Compare two configurations */
int Configcmp(const char *_a,const char *_b)
{
  const Config *a = (Config *) _a;
  const Config *b = (Config *) _b;
  int x;
  x = a->rp->index - b->rp->index;
  if( x==0 ) x = a->dot - b->dot;
  return x;
}

struct ConfigEqual
{
  size_t operator()(const Config* a, const Config* b) const
  {
    return Configcmp(reinterpret_cast<const char*>(a), reinterpret_cast<const char*>(b))==0;
  }
};

bool ConfigCompare(const Config* a, const Config* b)
{
  return Configcmp(reinterpret_cast<const char*>(a), reinterpret_cast<const char*>(b))<0;
}

std::unordered_set<Config*, ConfigHash, ConfigEqual> g_config_table;


/* Return a pointer to a new configuration */
PRIVATE Config *newconfig(){
  Config *newcfg;
  if (freelist==0) {
    int amt = 3;
    freelist = new Config[amt];
    if (freelist==0) {
      fprintf(stderr,"Unable to allocate memory for a new configuration.");
      exit(1);
    }
    for (int i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
    freelist[amt-1].next = 0;
  }
  newcfg = freelist;
  freelist = freelist->next;
  return newcfg;
}

/* The configuration "old" is no longer used */
PRIVATE void deleteconfig(Config *old)
{
  old->next = freelist;
  freelist = old;
}

/* Initialize the configuration list builder */
void Configlist_reset(){
  g_configs.clear();
  g_basis_configs.clear();
  g_config_table.clear();
  return;
}

/* Add another configuration to the configuration list */
Config *Configlist_add(
  Rule *rp,    /* The rule */
  int dot             /* Index into the RHS of the rule where the dot goes */
){
  Config *cfp, model;

  model.rp = rp;
  model.dot = dot;
  auto it = g_config_table.find(&model);
  if (it == g_config_table.end()) {
    cfp = newconfig();
    cfp->rp = rp;
    cfp->dot = dot;
    cfp->fws = SetNew();
    cfp->stp = 0;
    cfp->next = 0;
    g_configs.push_back(cfp);
    g_config_table.insert(cfp);
  } else {
    cfp = *it;
  }
  return cfp;
}

/* Add a basis configuration to the configuration list */
Config *Configlist_addbasis(Rule *rp, int dot)
{
  Config *cfp, model;

  model.rp = rp;
  model.dot = dot;
  auto it = g_config_table.find(&model);
  if (it == g_config_table.end()) {
    cfp = newconfig();
    cfp->rp = rp;
    cfp->dot = dot;
    cfp->fws = SetNew();
    cfp->stp = 0;
    cfp->next = 0;
    g_configs.push_back(cfp);
    g_basis_configs.push_back(cfp);
    g_config_table.insert(cfp);
  } else {
    cfp = *it;
  }
  return cfp;
}

/* Compute the closure of the configuration list */
void Configlist_closure(Lemon *lemp)
{
  for (Config* cfg : g_configs) {
    Rule* rule = cfg->rp;
    int dot = cfg->dot;
    if (dot >= rule->rhs.size()) continue;
    Symbol* sym = rule->rhs[dot];
    if (sym->type == NONTERMINAL) {
      if (sym->rules.empty() && sym != lemp->errsym) {
        ErrorMsg(lemp->filename, rule->line, "Nonterminal \"%s\" has no rules.",
          sym->name);
        lemp->errorcnt++;
      }
      for (Rule* newrp : sym->rules) {
        Config* newcfg = Configlist_add(newrp, 0);
        int i;
        for (i = dot+1; i < rule->rhs.size(); i++) {
          Symbol* xsym = rule->rhs[i];
          if (xsym->type == TERMINAL) {
            SetAdd(newcfg->fws, xsym->index);
            break;
          } else if (xsym->type==MULTITERMINAL) {
            for (Symbol* subsym : xsym->subsyms) {
              SetAdd(newcfg->fws, subsym->index);
            }
            break;
          } else {
            SetUnion(newcfg->fws, xsym->firstset);
            if (xsym->lambda == false)
              break;
          }
        }
        if (i == rule->rhs.size())
          cfg->fplp.push_front(newcfg);
      }
    }
  }
  return;
}

/* Sort the configuration list */
void Configlist_sort(){
  g_configs.sort(ConfigCompare);
}

/* Sort the basis configuration list */
void Configlist_sortbasis(){
  g_basis_configs.sort(ConfigCompare);
}

/* Return a pointer to the head of the configuration list and
** reset the list */
ConfigList& Configlist_return(){
  return g_configs;
}

/* Return a pointer to the head of the configuration list and
** reset the list */
ConfigList& Configlist_basis(){
  return g_basis_configs;
}

/* Free all elements of the given configuration list */
void Configlist_eat(const ConfigList& configs)
{
  for (Config* cfp : configs) {
    assert( cfp->fplp.empty() );
    assert( cfp->bplp.empty() );
    if (cfp->fws) SetFree(cfp->fws);
    deleteconfig(cfp);
  }
  return;
}
